package DP.回溯先;

/**
 * 最终总结 -> 无图无真相
 *  没有草稿 纯浪费时间
 *      1 脑袋瞎想 - 有用信息未收集
 *      2 没有索引依据 - debug找错误
 *
 */
class Solution {
    int maxPrice = Integer.MIN_VALUE;
    int[] p;
    int n;
    int[] vis;
    public int rob(int[] nums) {
        p = nums;
        n = nums.length;
        vis = new int[n]; // 偷或不偷？

        return backTrack(0);
    }
    public int backTrack(int sI) {
        // 末 也符合 间隔偷
        if (sI == n - 1) { // 最值 int f() 到 n-1
            return p[sI];
        }
        int maxOfFor = Integer.MIN_VALUE; // for用的max
        for (int i = sI; i < n; i++) {
            int curPrice = backTrack(i + 1);
            int toule = 0;
            int butou = 0;
            //fa偷过了
            if(vis[i] == 1){
                backTrack(i+1);// 不用比 ，直接剪掉
            } // fa没被偷
            else if (vis[i] == 0) {
                // 可偷
                vis[i] = 1;
                toule = backTrack(i+1) + p[i];
                // 可不偷 -> 下一个就可偷，可能比上方偷了的总price多哦！
                vis[i] = 0;
                butou = backTrack(i+1);
                maxOfFor = Math.max(maxOfFor, Math.max(toule, butou));
            }
        }
        return maxOfFor; // 一个node结束？
    }
}